/// \file
/// The header file containing the solver template classes.
/// \par Subversion URI:
/// \$URL: http://doku.googlecode.com/svn/trunk/src/solver.hpp $
/// \version \$Rev: 27 $
/// \date    \$Date: 2012-03-19 20:24:11 +0000 (Mon, 19 Mar 2012) $

#include <iostream>

/// A constant defining the structure and logic of a Sudoku board.
#define N 3

#define NCELLS N*N*N*N
/// A field constant necessary for colouring.
#define FIELD ((1 << (N*N)) - 1)

/// Quick and dirty assert hack since the regular assert fucks the stack.
#define assert(a) {if(!a){int b=0;b/=b;}}

namespace solver {
	//////////////////////////////////////////////////////////////////////////
	class Parent;
	class Child;
	class Board;

	//////////////////////////////////////////////////////////////////////////
	/// A small automated list class.
	template <typename MemberType>
	class Aggregate {
	protected:
		Aggregate(unsigned nmembersinit) : nmembers(nmembersinit) {
			members = new MemberType*[nmembers];
			nadded = 0;
		}
	public:
		~Aggregate() {
			if (members) {
				delete [] members;
				members = 0;
			}
		}
		void AddMember(MemberType *member) {
			members[nadded++] = member;
		}
	protected:
		const unsigned nmembers;
		unsigned nadded;
		MemberType **members;
	};

	//////////////////////////////////////////////////////////////////////////
	/// A logical parent class with a set of referenced children.
	class Parent : public Aggregate<Child> {
	public:
		Parent(unsigned nchildren) : Aggregate(nchildren) {}
		void AddChild(Child *child);
		virtual void RecvExcludeUp(unsigned short x, const Child *sender);
		unsigned short GetSum() const;
		void Eliminate(unsigned short set = FIELD);
		bool IsValid() const;
	};

	//////////////////////////////////////////////////////////////////////////
	/// A logical child class with a set of referenced parents.
	class Child : public Aggregate<Parent> {
	protected:
		Child(unsigned nparents) : Aggregate(nparents) {
			isResolved = false;
		}
	public:
		void Copy(const Child &copy) {
			isResolved = copy.isResolved;
		}
		void Resolve() {
			Resolve(GetField());
		}
		virtual void Resolve(unsigned short x) {
			isResolved = true;
			SendExcludeUp(x, this);
		}
		bool IsResolved() const {
			return isResolved;
		}
		bool IsUnique() const {
			return IsUnique(GetField());
		}
		void CheckUnique() {
			unsigned short x = GetField();
			if (IsUnique(x))
				Resolve(x);
		}
		void SendExcludeUp(unsigned short x, const Child *sender) {
			for (unsigned i = 0; i < nmembers; i++)
				members[i]->RecvExcludeUp(x, sender);
		}
		virtual void RecvExcludeDown(unsigned short x, const Child *sender) {
			if (!IsResolved()) {
				DoExclusion(x, sender);
				CheckUnique();
			}
		}
		virtual void DoExclusion(unsigned short x, const Child *sender) = 0;
		virtual bool IsUnique(unsigned short x) const = 0;
		virtual unsigned short GetField() const = 0;
	protected:
		bool isResolved;
	};

	//////////////////////////////////////////////////////////////////////////
	/// A class to represent three subvectors in an NxN Sudoku box, of only
	/// one orientation (horizontal or vertical).
	class TopParent : public Parent {
	public:
		TopParent() : Parent(N) {}
	};

	//////////////////////////////////////////////////////////////////////////
	/// A class to represent a 1xN subvector in an NxN Sudoku box.
	class Subvector :
		public Parent,
		public Child {
	public:
		Subvector() : Parent(N), Child(2) {}
		void RecvExcludeUp(unsigned short x, const Child *sender) {
			Child::SendExcludeUp(x, sender);
		}
		void RecvExcludeDown(unsigned short x, const Child *sender) {
			Child::RecvExcludeDown(x, sender);
			Parent::RecvExcludeUp(x, sender);
		}
		void DoExclusion(unsigned short x, const Child *sender) {
			Parent::RecvExcludeUp(x, sender);
		}
		unsigned short GetField() const {
			return GetSum();
		}
		bool IsUnique(unsigned short x) const {
			unsigned bits = 0;
			do {
				if (x & 1)
					if (++bits > 3)
						return false;
				x >>= 1;
			} while (x);
			return true;
		}
		void Resolve(unsigned short x) {
			Parent::Eliminate(x);
			isResolved = Child::IsUnique();
			Child::SendExcludeUp(x, this);
		}
	};

	//////////////////////////////////////////////////////////////////////////
	/// A class representing a single cell in a Sudoku board.
	class Cell : public Child {
	public:
		Cell() : Child(2) {
			field = FIELD;
		}
		void Copy(const Cell &copy) {
			Child::Copy(copy);
			field = copy.field;
		}
		void Init(char c) {
			Resolve(1 << (c - '1'));
		}
		char GetChar() const {
			char n = '1';
			unsigned short ftest = field;
			while (ftest != 1) {
				ftest >>= 1;
				n++;
			}
			return n;
		}
		void Output(std::ostream &out, unsigned p) const {
			if (IsResolved()) {
				if (p == N/2)
					out << ' ' << GetChar() << ' ';
				else
					out << "   ";
			}
			else for (unsigned d = N*p; d < N*(p+1); d++)
				out << ((field & (1 << d)) ? ((char)('1' + d)) : '-');
		}
		unsigned short GetField() const {
			return field;
		}
		bool IsUnique(unsigned short x) const {
			if (!x)
				return false;
			while (!(x & 1))
				x >>= 1;
			return x == 1;
		}
		unsigned GetBitCount() const {
			unsigned bits = 0;
			for (unsigned x = field; x; x >>= 1)
				if (x & 1) ++bits;
			return bits;
		}
		void SetBoard(Board *boardinit) {
			board = boardinit;
		}
		void Resolve(unsigned short x);
		void DoExclusion(unsigned short x, const Child *sender);
	private:
		unsigned short field;
		Board *board;
	};

	//////////////////////////////////////////////////////////////////////////
	/// A class representing a Sudoku board.
	class Board {
	public:
		Board(std::istream &in) : lincells(&cells[0][0][0][0]) {
			resolvedcells = 0;
			solvable = true;
			SetLinks();
			InitFromStream(in);
		}
		Board(const Board &copy);
		bool IsSolvable() const {
			return solvable;
		}
		void IncrementSolved() {
			resolvedcells++;
		}
		void MarkUnsolvable() {
			solvable = false;
		}
		void FinishSolve(std::ostream &out);
		void Output(std::ostream &out, bool line = false) const;
		bool IsValid() const;
	private:
		void SetLinks();
		void InitFromStream(std::istream &in);
		void SolveRecurse(std::ostream &out, unsigned startcell, unsigned depth = 0);
		void Eliminate();
		void Guess(std::ostream &out, unsigned startcell, unsigned depth) const;
	private:
		TopParent rows[N][N];		// Y y
		TopParent cols[N][N];		// X x
		TopParent boxrows[N][N];	// Y X
		TopParent boxcols[N][N];	// Y X
		Subvector subrows[N][N][N];	// Y X y
		Subvector subcols[N][N][N];	// Y X x
		Cell cells[N][N][N][N];		// Y y X x
		Cell *const lincells;
		unsigned resolvedcells;
		bool solvable;
		static unsigned solutions;
	};
}
